//
// Created by wormtql on 2020/11/8.
//

#include <map>
#include <string>
#include <cstring>
#include <fstream>
#include <queue>
#include <vector>
#include <sstream>
#include <iostream>
#include <set>
#include <cmath>
#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

struct Edge {
    int to;
    int from;
    int next;
};

set<int> blacklist;

#ifdef REMOTE
int dis_cache[11000][11000] = { 0 };
#else
int dis_cache[1000][1000] = { 0 };
#endif
map<string, int> function_name_to_index;

// 图
#ifdef REMOTE
Edge edges[5000000];
int edge_count = 0;
int head[600000];
int node_count = 0;
int dis[600000];
int vis[600000];
int parent[600000];
#else
Edge edges[2000000];
int edge_count = 0;
int head[500000];
int node_count = 0;
int dis[500000];
int vis[500000];
int parent[500000];
#endif
map<string, int> name2id;
map<int, string> id2name;

int trace_count = 0;
vector<int> traces[6000];

// trace总node数
int trace_node_count = 0;
int trace_found_node_count = 0;

int mat_start = 0;
int mat_end = 10000;


void init() {
    memset(edges, -1, sizeof(edges));
    memset(head, -1, sizeof(head));
    edge_count = 0;
    node_count = 0;
    name2id.clear();

    trace_node_count = 0;
    trace_found_node_count = 0;
}

bool parseLine(const char * line, char * from, char * to) {
    int i = 0;
    bool flag = false;
    bool isFrom = true;

    int a = 0;
    int b = 0;

    while (line[i] != '\0') {
        if (line[i] == '\"') {
            if (!flag) {
                flag = true;
            } else {
                if (!isFrom) {
                    break;
                }
                flag = false;
                isFrom = false;
            }
            i++;
            continue;
        }

        if (flag) {
            if (isFrom) {
                from[a] = line[i];
                a++;
            } else {
                to[b] = line[i];
                b++;
            }
        }
        i++;
    }

    if (a == 0 || b == 0) {
        return false;
    }

    from[a] = 0;
    to[b] = 0;

    return true;
}

void parse_csv_line(char * line, vector<string> & data) {
    int state = 0;
    char buf[1000] = { 0 };
    int l = 0;

    int i = 0;
    while (line[i]) {
        if (state == 0) {
            if (line[i] == ',') {
                state = 1;
            } else {
                buf[l++] = line[i];
                i++;
            }
        } else if (state == 1) {
            buf[l] = 0;
            l = 0;
            data.push_back(string(buf));
            i++;
            state = 0;
        }
    }
    if (l != 0) {
        buf[l] = 0;
        data.emplace_back(buf);
    }
}

bool load_traces(char * filename, int limit) {
    ifstream file(filename);
    if (!file.is_open()) {
        return false;
    }

    char buf[10000];
    while(file.getline(buf, 10000) && trace_count < limit) {
//        char version[100];
//        char commit_id[100];
        vector<string> ts;
//        parse_trace_line(buf, version, commit_id, ts);
        parse_csv_line(buf, ts);

        for (const string & s: ts) {
//            printf("%s\n", s.c_str());
            if (name2id.find(s) != name2id.end()) {
                trace_found_node_count++;
                traces[trace_count].push_back(name2id[s]);
            }
            trace_node_count++;
        }

        trace_count++;
    }

    return true;
}

int register_node(char * name) {
    string temp(name);
    if (name2id.find(temp) == name2id.end()) {
        name2id[name] = node_count;
        id2name[node_count] = name;
        node_count++;
        return node_count - 1;
    } else {
        return name2id[temp];
    }
}

void add(int from, int to) {
    edges[edge_count].from = from;
    edges[edge_count].to = to;
    edges[edge_count].next = head[from];
    head[from] = edge_count;
    edge_count++;
}

bool load_graph(char * filename) {
    ifstream file(filename);

    if (!file.is_open()) {
        return false;
    }

    char line[1000] = { 0 };
    while(file.getline(line, 1000)) {
        char from[100] = { 0 };
        char to[100] = { 0 };

        bool ret = parseLine(line, from, to);
        if (!ret) {
            printf("aaa\n");
            continue;
        }

        int from_id = register_node(from);
        int to_id = register_node(to);
        add(from_id, to_id);
    }

    return true;
}

void sp_single(int a) {
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(parent, -1, sizeof(parent));

    for (auto i = blacklist.begin(); i != blacklist.end(); i++) {
//        if (id2name.find(*i) != id2name.end()) {
            vis[*i] = 1;
//        }
    }

    if (vis[a] == 1) {
        memset(dis, INF, sizeof(dis));
    }

    queue<int> q;
    q.push(a);
    dis[a] = 0;
    vis[a] = 1;

    while(!q.empty()) {
        int p = q.front();
        q.pop();

        for (int e = head[p]; e != -1; e = edges[e].next) {
            int to = edges[e].to;

            if (!vis[to]) {
                q.push(to);
                vis[to] = 1;
                dis[to] = dis[p] + 1;
                parent[to] = p;
            }
        }
    }
}

void load_blacklist(char * filename) {
    ifstream file(filename);

    char c;
    char buf[1000] = { 0 };
    int l = 0;

    while (file >> c) {
        if (c != ',') {
            buf[l++] = c;
        } else {
            buf[l] = 0;
            l = 0;
            string temp(buf);
//            cout << temp << endl;
            if (name2id.find(temp) != name2id.end()) {
                blacklist.insert(name2id[temp]);
            }
        }
    }

    if (l != 0) {
        buf[l] = 0;
        string temp(buf);
        blacklist.insert(name2id[temp]);
    }
}

void get_sp(int from, int to, vector<string> & path) {
    if (from == to) {
//        printf("%s\n", id2name[from].c_str());
        path.push_back(id2name[from]);
        return;
    }

    get_sp(from, parent[to], path);
//    printf("%s\n", id2name[to].c_str());
    path.push_back(id2name[to]);
}

int main(int argc, char * argv[]) {
#ifdef REMOTE
    printf("running remotely\n");
#endif
    if (argc < 7) {
        printf("count how many times a function accurs in every two node\n\n");
        printf("app <graph.dot> <calltrace.csv> <blacklist> <start> <end+1> <outfile>\n\n");
        printf("graph.dot:          call graph\n");
        printf("calltrace.csv:      call trace\n");
        printf("blacklist:          black list\n");
        printf("start, end:         ...\n");
        printf("outfile:            output matrix\n");
        return 0;
    }

    init();


    // start end
    mat_start = atoi(argv[4]);
    mat_end = atoi(argv[5]);

    // load graph
    bool ret = load_graph(argv[1]);
    if (!ret) {
        printf("unable to open file \"%s\"\n", argv[1]);
    }
    printf("graph loaded\n");
    printf("node count: %d\n", node_count);
    printf("edge count: %d\n", edge_count);

    // load traces
    load_traces(argv[2], 10000);
    printf("\ntraces loaded\n");
    printf("trace count: %d\n", trace_count);
    printf("trace node count: %d\n", trace_node_count);
    printf("found trace node count: %d\n", trace_found_node_count);
    printf("rate: %.6lf\n", 1.0 * trace_found_node_count / trace_node_count);


    load_blacklist(argv[3]);

    mat_end = min(mat_end, trace_count);



    map<string, int> stats;
    for (int i = mat_start; i < mat_end; i++) {
        if (traces[i].size() != 0) {
            sp_single(traces[i][0]);
            for (int j = 0; j < trace_count; j++) {
                if (traces[j].size() != 0 && dis[traces[j][0]] < INF) {
                    if (blacklist.find(traces[i][0]) != blacklist.end() || blacklist.find(traces[j][0]) != blacklist.end()) {
                        continue;
                    }
                    vector<string> temp;
                    get_sp(traces[i][0], traces[j][0], temp);
                    for (auto & name: temp) {
                        stats[name]++;
                    }
                }
            }
        }

        printf("%.6lf%%\n", (i + 1.0 - mat_start) / (mat_end - mat_start) * 100);
    }

    vector<pair<string, int>> temp;
    for (auto & i: stats) {
        temp.push_back(i);
    }
    sort(temp.begin(), temp.end(), [](const pair<string, int> & a, const pair<string, int> & b) {
        return a.second > b.second;
    });

    ofstream out_file(argv[6]);
    for (auto i: temp) {
        out_file << i.first << " " << i.second << endl;
    }
    out_file.close();

    return 0;
}